//////////////////////////////////////
// Fast Container Library           //
// MIT License - Copyright (c) 2012 //
//////////////////////////////////////

#pragma once

#include "common.h"
#include "allocator.h"
#include "circular_buffer.h"
#include "forward.h"


FC_NAMESPACE_BEGIN


template <class T, class Allocator>
class deque : public circular_buffer<T, Allocator>
{
public:
	typedef deque<T, Allocator>								this_type;
	typedef circular_buffer<T, Allocator>					base_type;
	typedef size_t											size_type;
	typedef T												value_type;
	typedef T*												pointer;
	typedef const T*										const_pointer;
	typedef T&												reference;
	typedef const T&										const_reference;
	typedef typename base_type::iterator					iterator;
	typedef typename base_type::const_iterator				const_iterator;
	typedef typename base_type::reverse_iterator			reverse_iterator;
	typedef typename base_type::const_reverse_iterator		const_reverse_iterator;
	typedef typename base_type::allocator_type				allocator_type;
	typedef ptrdiff_t										difference_type;

	using base_type::begin;
	using base_type::end;
	using base_type::cbegin;
	using base_type::cend;
	using base_type::rbegin;
	using base_type::rend;
	using base_type::size;
	using base_type::empty;
	using base_type::full;
	using base_type::capacity;
	using base_type::get_allocator;
	using base_type::set_allocator;
	using base_type::clear;
	using base_type::reset;
	using base_type::front;
	using base_type::back;
	using base_type::pop_back;
	using base_type::pop_front;
	using base_type::assign;
	using base_type::reserve;
	using base_type::set_capacity;
	using base_type::shrink_to_fit;
	using base_type::iterator_is_valid;
	using base_type::swap;
	using base_type::at;
	using base_type::operator[];
	using base_type::make_linear;
	using base_type::increment;
	using base_type::decrement;
	using base_type::increment_offset;
	using base_type::decrement_offset;
	using base_type::linear_offset;
	using base_type::get_head;
	using base_type::get_tail;

	using base_type::m_data;
	using base_type::m_head;
	using base_type::m_tail;
	using base_type::m_capacity;
	using base_type::m_size;

	// friend iterator class access
	template <class Q, class U, class V> friend class circular_buffer_iterator;

	deque()
		: base_type()
		{
		}

	deque( const allocator_type& alloc )
		: base_type(alloc)
		{
		}

	template <class InputIterator>
	deque( InputIterator first, InputIterator last )
		: base_type(first, last)
		{
		}

	deque( size_t n, const T& value )
		: base_type(n, value)
		{
		}

	deque( const this_type& d )
		: base_type(d)
		{
		}

	void resize( size_t n, const T& value = T() )
	{
		// always respect the capacity request by the user.
		reserve(n);

		if( n > m_size )
			insert_n( end(), n - m_size, value );
		else if( n < m_size )
			erase( begin() + n, end() );
	}

	void push_back( const T& value = T() )
	{
		if( FC_UNLIKELY(full()) )
			grow();

		fc::construct(m_tail, value);
		increment(m_tail);
		++m_size;
	}

	void push_front( const T& value = T() )
	{
		if( FC_UNLIKELY(full()) )
			grow();

		decrement(m_head);
		fc::construct(m_head, value);
		++m_size;
	}

	template <class InputIterator>
	void insert( iterator pos, InputIterator first, InputIterator last )
	{
		InsertDispatch( pos, first, last,
			typename fc::is_integral<InputIterator>::type() );
	}

	template <class InputIterator>
	void insert_iter( iterator pos, InputIterator first, InputIterator last )
	{
		InsertIterator( pos, first, last, typename is_pod<T>::type() );
	}

	void insert_n( iterator pos, size_t n, const T& value ) { insert( pos, n, value ); }
	void insert( iterator pos, size_t n, const T& value )
	{
		InsertValues( pos, n, value, typename is_pod<T>::type() );
	}

	iterator insert( iterator pos, const T& value )
	{
		return InsertValue(pos, value);
	}

	iterator insert_front( iterator it, const T& value )
	{
		if( full() )
			grow();

		return it;
	}

	iterator insert_back( iterator it, const T& value )
	{
		if( full() )
			grow();

		return it;
	}

	iterator erase( iterator first, iterator last )
	{
		if( first - begin() < ptrdiff_t(m_size >> 1) )
			return erase_front(first, last);

		return erase_back(first, last); //FIXME
	}

	iterator erase_back( iterator first, iterator last )
	{
		const size_t n = size_t(last - first);
		iterator p = fc::copy( last, end(), first );
		fc::destroy_range( p, end() );
		m_tail = decrement_offset(m_tail, n);
		m_size -= n;

		return first;
	}

	iterator erase_front( iterator first, iterator last )
	{
		const size_t n = size_t(last - first);
		iterator p = fc::copy_backward( begin(), first, last );
		fc::destroy_range( begin(), p );
		m_head = increment_offset(m_head, n);
		m_size -= n;

		return last;
	}

	iterator erase( iterator pos )
	{
		if( pos - begin() < end() - pos )
			return erase_front(pos);

		return erase_back(pos);
	}

	iterator erase_back( iterator pos )
	{
		iterator p = fc::copy( pos + 1, end(), pos );
		pop_back();
		return pos;
	}

	iterator erase_front( iterator pos )
	{
		iterator p = fc::copy_backward( begin(), pos + 1, pos );
		pop_front();
		return pos;
	}

	void grow( size_t minimumGrowth = 1 )
	{
		size_t newCapacity = get_new_capacity(minimumGrowth);
		set_capacity(newCapacity);
	}

	size_t get_new_capacity( size_t minimumGrowth ) const
	{
		const size_t oldCapacity = size_t(m_capacity - m_data);
		return fc::max(
			fc::max<size_t>(oldCapacity * 2, oldCapacity + minimumGrowth),
			fc::max<size_t>(minimumGrowth * 2, FC_MIN_VECTOR_GROWTH * 4)
		);
	}

protected:
	template <typename InputIterator>
	void InsertDispatch( iterator pos, InputIterator first, InputIterator last, const false_type& )
	{
		InsertIterator( pos, first, last, typename is_pod<InputIterator>::type() );
	}

	template <class Integral>
	inline void InsertDispatch( iterator pos, Integral n, Integral value, const true_type& )
	{
		InsertValues( pos, n, value, typename is_pod<T>::type() );
	}

	T* InsertReallocate( iterator pos, size_t n )
	{
		const size_t newCapacity = get_new_capacity(n);
		T* newBegin = allocate(newCapacity);

		T* newPos = fc::uninitialized_copy( begin(), pos, newBegin );
		T* newEnd = fc::uninitialized_copy( pos, end(), newPos + n );

		fc::destroy_range( begin(), end() );
		base_type::deallocate();

		m_data = newBegin;
		m_head = newBegin;
		m_tail = newEnd;
		m_capacity = newBegin + newCapacity;
		m_size += n;

		return newPos;
	}

	iterator InsertValue( iterator pos, const T& value )
	{
		FC_ASSERT(iterator_is_valid(pos));
		const T temp(value);

		if( FC_LIKELY(m_size != size_t(m_capacity - m_data)) ) //if we have enough room
		{
			pos.normalize();

			if( pos.ptr == m_tail ) //insert at end
			{
				//pos.ptr = m_tail;
				fc::construct( m_tail, value );
				increment(m_tail);
			}
			// insert by moving range either left or right.
			else if( pos - begin() < end() - pos )
			{
				T* first = m_head;
				decrement(m_head);
				fc::construct( m_head, *first );
				fc::copy( iterator(this, first), pos, begin() );
				*--pos = temp;
			}
			else
			{
				//increment(m_tail);

				T* last = get_tail();
				fc::construct( m_tail, *get_tail() );
				//increment(m_tail);


				fc::copy_backward( pos, iterator(this, m_tail), end() );
				//fc::copy_backward( pos, iterator(this, m_tail), end() );

				//fc::copy_backward( pos, end(), end() );
				increment(m_tail);
				*pos = temp;
			}

			++m_size;
		}
		else
		{
			T* p = InsertReallocate( pos, size_t(1) );
			fc::construct(p, temp);
			pos.ptr = p;
		}

		return pos;
	}

	template <class ForwardIterator>
	void InsertIterator( iterator pos, ForwardIterator first, ForwardIterator last, true_type )
	{
		FC_ASSERT(iterator_is_valid(pos));

		const size_t n = fc::distance( first, last );
		pos.normalize();

		if( FC_LIKELY(n + m_size < size_t(m_capacity - m_data)) )
		{
			if( pos - begin() < end() - pos )
			{
				fc::copy( begin(), pos, begin() - n );
				fc::copy( first, last, pos - n );

				m_head = decrement_offset( m_head, n );
				m_size += n;
			}
			else
			{
				m_tail = increment_offset( m_tail, n );
				m_size += n;

				fc::copy_backward( pos, end() - n, end() );
				fc::copy( first, last, pos );
			}
		}
		else
		{
			T* p = InsertReallocate( pos, n );
			fc::copy( first, last, p );
		}
	}

	template <class ForwardIterator>
	void InsertIterator( iterator pos, ForwardIterator first, ForwardIterator last, false_type )
	{
		FC_ASSERT(iterator_is_valid(pos));
		size_t n = fc::distance( first, last );

		/*
		if( pos.ptr == 0 )
		{
			m_tail = increment_offset( m_tail, n );
			m_size += n;
			fc::uninitialized_copy( first, last, iterator(this, m_tail) );
		}
		else
		if( pos.ptr == m_head )
		{
			fc::uninitialized_copy( first, last, begin() - n );
			m_head = decrement_offset( m_head, n );
			m_size += n;
		}
		else
		*/

		pos.normalize();

		if( FC_LIKELY(n + m_size < size_t(m_capacity - m_data)) )
		{
			//iterator itBegin, itEnd;
			const size_t left = size_t(pos - begin());
			const size_t right = size_t(end() - pos);
			if( left < right )
			{
				iterator oldBegin(this, m_head);
				m_head = decrement_offset( m_head, n );
				m_size += n;

				if( n <= left )
				{
					//iterator oldBegin(this, m_head);
					iterator diff = oldBegin + n;
					fc::uninitialized_copy( oldBegin, diff, begin() );
					fc::copy( diff, pos, oldBegin );
					fc::copy( first, last, pos - n );
				}
				else
				{
					fc::uninitialized_copy( oldBegin, pos, begin() );

					ForwardIterator mid = first;
					fc::advance( mid, left );
					fc::uninitialized_copy( first, mid, pos - n );
					fc::copy( mid, last, pos - n + left );
				}

				//m_head = decrement_offset( m_head, n );
				//m_size += n;
			}
			else
			{
				iterator oldEnd(this, m_tail);
				m_tail = increment_offset( m_tail, n );
				m_size += n;

				//const size_t right = size_t(oldEnd - pos);
				if( n <= right )
				{
					iterator diff = oldEnd - n;
					fc::uninitialized_copy( diff, oldEnd, end() );
					fc::copy_backward( pos, diff, oldEnd );
					fc::copy( first, last, pos );
				}
				else
				{
					fc::uninitialized_copy( pos, oldEnd, end() - right );

					ForwardIterator mid = first;
					fc::advance( mid, right );
					fc::copy( first, mid, pos );
					fc::uninitialized_copy( mid, last, oldEnd );
				}
			}
		}
		else
		{
			T* p = InsertReallocate( pos, n );
			fc::uninitialized_copy( first, last, p );
		}
	}

	void InsertValues( iterator pos, size_t n, const T& value, true_type )
	{
		FC_ASSERT(iterator_is_valid(pos));
		//iterator newEnd = end() + n;

		const value_type temp = value;

		// if we have enough room...
		if( FC_LIKELY(n + m_size < size_t(m_capacity - m_data)) )
		{
			pos.normalize();
			/*
			if( pos.ptr == 0 ) // if pos == end()
			{
				fc::fill_n( iterator(this, m_tail), n, value );
				m_tail = increment_offset( m_tail, n );
				m_size += n;
			}
			*/

			// if we should insert from beginning.
			//else
			if( pos - begin() < end() - pos )
			{
				fc::copy( begin(), pos, begin() - n );
				fc::fill_n( pos - n, n, temp );

				m_head = decrement_offset( m_head, n );
				m_size += n;
			}

			// insert range at end.
			else
			{
				iterator oldEnd = iterator( this, m_tail );
				m_tail = increment_offset( m_tail, n );
				m_size += n;

				fc::copy_backward( pos, oldEnd, end() );
				fc::fill_n( pos, n, temp );
			}
		}
		else // out of storage - reallocate and fill hole with value.
		{
			T* p = InsertReallocate( pos, n );
			fc::fill_n( p, n, temp );
		}
	}

	void InsertValues( iterator pos, size_t n, const T& value, false_type )
	{
		FC_ASSERT(iterator_is_valid(pos));
		iterator newEnd = end() + n;

		/*
		else
		if( it == end() )
		{
			fc::uninitialized_fill_n( end(), n, value );
			m_tail = increment_offset( m_tail, n );
			m_size += n;
		}
		*/

		if( FC_LIKELY(n + m_size < size_t(m_capacity - m_data)) )
		{
			pos.normalize();

			if( pos - begin() < end() - pos )
			{
				iterator oldEnd = iterator( this, m_tail );
				m_tail = increment_offset( m_tail, n );
				m_size += n;

				const value_type tmp = value;
				const size_t rpos = size_t(end() - pos);
				if( n <= rpos )
				{
					iterator diff = oldEnd - n;
					fc::uninitialized_copy( diff, oldEnd, oldEnd );
					fc::copy_backward( pos, diff, oldEnd );
					fc::fill_n( pos, n, tmp );
				}
				else
				{
					fc::uninitialized_copy_backward( pos, oldEnd, end() );
					fc::uninitialized_fill_n( oldEnd, n - rpos, tmp );
					fc::fill_n( pos, rpos, tmp );
				}
			}
			else
			{
				//todo
			}
		}
		else // out of storage - reallocate and fill hole with value.
		{
			T* p = InsertReallocate( pos, n );
			fc::uninitialized_fill_n( p, n, value );
		}
	}

};


FC_NAMESPACE_END
